package com.xiaolin.algorithm.sort;

import java.util.Arrays;

/**
 * @ClassName HeapSort
 * @Description 堆排序
 * @Detail      堆是一种特殊的完全二叉树，其父节点大于左右子节点的称为大顶推，其父节点小于左右子节点称为小顶堆
 *                 推可以存放在数组，也可以使用指针进行元素关联
 *                 堆的两个公式：
 *                  大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
 *                  小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]
 *                 一般升序采用大顶堆，降序采用小顶堆
 *
 * @Author MyPC
 * @Date 2020/8/7
 * @Version 1.0
 */
public class HeapSort {

    public static void main(String[] args) {
        int []arr = {9,83,6,13,4,3,2,1,3,12,55};
        System.out.println(Arrays.toString(sort(arr)));;
    }

    /**
     * 排序
     * @param arr
     * @return
     */
    public static int[] sort(int[] arr){
        // 构建一个大顶堆
        buildHeap(arr, arr.length);
        for(int i=1;i<arr.length;i++){
            // 每次构建完大顶堆，将第一个元素与大顶堆最后一个元素替换
            int temp=arr[0];
            arr[0]=arr[arr.length-i];
            arr[arr.length-i]=temp;
            // 构建新的大顶堆
            buildHeap(arr,arr.length-i);
        }
        return arr;
    }

    /**
     * 构建堆
     * @param arr  待构建的堆
     * @param heapSize  待构建的堆的个数
     * @return
     */
    public static void buildHeap(int[] arr,int heapSize){
        // 最后一个非叶子节点的索引下标
        int notChild=heapSize/2-1;
        // 先排好最后一个非叶子节点的顺序
        for(int i=notChild;i>=0;i--){
            // 存放非叶子节点值
            int temp=arr[i];
            // 第一次是非叶子节点的元素大小判断，之后是被替换的节点的元素大小判断
            for(int j=i*2+1;j<heapSize;j=j*2+1){
                if(j+1<heapSize && arr[j]<arr[j+1]){
                    // 左子节点小于右子节点，说明又节点可能被替换，标记右节点
                    j=j+1;
                }
                if(arr[j] > temp){
                    // 父节点小于子节点，进行替换
                    arr[i]=arr[j];
                    // 记录被替换的节点位置
                    i=j;
                }else {
                    // 如果父子节点没有进行交换，直接终止循环
                    break;
                }
            }
            // 将原来的非叶子节点的值存到最后被替换的节点上
            arr[i]=temp;
        }
    }

}
